//-----------------------------------------------------------------------------
// File: Linklist.h
// Desc: Linked list class.
//
// THIS CODE AND INFORMATION IS PROVIDED "AS IS" WITHOUT WARRANTY OF
// ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO
// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A
// PARTICULAR PURPOSE.
//
//  Copyright (C) Microsoft Corporation. All rights reserved.
//-----------------------------------------------------------------------------

#pragma once

#include <new>
#include <assert.h>

namespace Classes
{

	/*---------------------------------------------------------------------

	ComPtrList template

	Implements a list of COM pointers.

	Template parameters:

	T:        COM interface type.

	NULLABLE: If true, client can insert NULL pointers. By default,
	the list does not allow NULL pointers.

	Examples:

	ComPtrList<IUnknown>
	ComPtrList<IUnknown, TRUE>


	The list supports enumeration:

	for (ComPtrList<IUnknown>::POSIITON pos = list.FrontPosition();
	pos != list.EndPosition();
	pos = list.Next(pos))
	{
	IUnknown *pUnk = NULL;

	hr = list.GetItemByPosition(pos, &pUnk);

	if (SUCCEEDED(hr))
	{
	pUnk->Release();
	}
	}

	The list is implemented as a double-linked list with an anchor node.

	---------------------------------------------------------------------*/

	template <class T>
	struct NoOp
	{
		void operator()(T& t)
		{
		}
	};

	template <class T>
	class List
	{
	protected:

		// Nodes in the linked list
		struct Node
		{
			Node *prev;
			Node *next;
			T    item;

			Node() : prev(NULL), next(NULL)
			{
			}

			Node(T item) : prev(NULL), next(NULL)
			{
				this->item = item;
			}

			T Item() const { return item; }
		};

	public:

		// Object for enumerating the list.
		class POSITION
		{
			friend class List<T>;

		public:
			POSITION() : pNode(NULL)
			{
			}

			bool operator==(const POSITION &p) const
			{
				return pNode == p.pNode;
			}

			bool operator!=(const POSITION &p) const
			{
				return pNode != p.pNode;
			}

		private:
			const Node *pNode;

			POSITION(Node *p) : pNode(p) 
			{
			}
		};

	protected:
		Node    m_anchor;  // Anchor node for the linked list.
		DWORD   m_count;   // Number of items in the list.

		Node* Front() const
		{
			return m_anchor.next;
		}

		Node* Back() const
		{
			return m_anchor.prev;
		}

		virtual HRESULT InsertAfter(T item, Node *pBefore)
		{
			if (pBefore == NULL)
			{
				return E_POINTER;
			}

			Node *pNode = new Node(item);
			if (pNode == NULL)
			{
				return E_OUTOFMEMORY;
			}

			Node *pAfter = pBefore->next;

			pBefore->next = pNode;
			pAfter->prev = pNode;

			pNode->prev = pBefore;
			pNode->next = pAfter;

			m_count++;

			return S_OK;
		}

		virtual HRESULT GetItem(const Node *pNode, T* ppItem)
		{
			if (pNode == NULL || ppItem == NULL)
			{
				return E_POINTER;
			}

			*ppItem = pNode->item;
			return S_OK;
		}

		// RemoveItem:
		// Removes a node and optionally returns the item.
		// ppItem can be NULL.
		virtual HRESULT RemoveItem(Node *pNode, T *ppItem)
		{
			if (pNode == NULL)
			{
				return E_POINTER;
			}

			assert(pNode != &m_anchor); // We should never try to remove the anchor node.
			if (pNode == &m_anchor)
			{
				return E_INVALIDARG;
			}


			T item;

			// The next node's previous is this node's previous.
			pNode->next->prev = pNode->prev;

			// The previous node's next is this node's next.
			pNode->prev->next = pNode->next;

			item = pNode->item;
			delete pNode;

			m_count--;

			if (ppItem)
			{
				*ppItem = item;
			}

			return S_OK;
		}

	public:

		List()
		{
			m_anchor.next = &m_anchor;
			m_anchor.prev = &m_anchor;

			m_count = 0;
		}

		virtual ~List()
		{
			Clear();
		}

		// Insertion functions
		HRESULT InsertBack(T item)
		{
			return InsertAfter(item, m_anchor.prev);
		}


		HRESULT InsertFront(T item)
		{
			return InsertAfter(item, &m_anchor);
		}

		// RemoveBack: Removes the tail of the list and returns the value.
		// ppItem can be NULL if you don't want the item back. (But the method does not release the item.)
		HRESULT RemoveBack(T *ppItem)
		{
			if (IsEmpty())
			{
				return E_FAIL;
			}
			else
			{
				return RemoveItem(Back(), ppItem);
			}
		}

		// RemoveFront: Removes the head of the list and returns the value.
		// ppItem can be NULL if you don't want the item back. (But the method does not release the item.)
		HRESULT RemoveFront(T *ppItem)
		{
			if (IsEmpty())
			{
				return E_FAIL;
			}
			else
			{
				return RemoveItem(Front(), ppItem);
			}
		}

		// GetBack: Gets the tail item.
		HRESULT GetBack(T *ppItem)
		{
			if (IsEmpty())
			{
				return E_FAIL;
			}
			else
			{
				return GetItem(Back(), ppItem);
			}
		}

		// GetFront: Gets the front item.
		HRESULT GetFront(T *ppItem)
		{
			if (IsEmpty())
			{
				return E_FAIL;
			}
			else
			{
				return GetItem(Front(), ppItem);
			}
		}


		// GetCount: Returns the number of items in the list.
		DWORD GetCount() const { return m_count; }

		bool IsEmpty() const
		{
			return (GetCount() == 0);
		}

		// Clear: Takes a functor object whose operator()
		// frees the object on the list.
		template <class FN>
		void Clear(FN& clear_fn)
		{
			Node *n = m_anchor.next;

			// Delete the nodes
			while (n != &m_anchor)
			{
				clear_fn(n->item);

				Node *tmp = n->next;
				delete n;
				n = tmp;
			}

			// Reset the anchor to point at itself
			m_anchor.next = &m_anchor;
			m_anchor.prev = &m_anchor;

			m_count = 0;
		}

		// Clear: Clears the list. (Does not delete or release the list items.)
		virtual void Clear()
		{
			Clear<NoOp<T>>(NoOp<T>());
		}


		// Enumerator functions

		POSITION FrontPosition()
		{
			if (IsEmpty())
			{
				return POSITION(NULL);
			}
			else
			{
				return POSITION(Front());
			}
		}

		POSITION EndPosition() const
		{
			return POSITION();
		}

		HRESULT GetItemPos(POSITION pos, T *ppItem)
		{   
			if (pos.pNode)
			{
				return GetItem(pos.pNode, ppItem);
			}
			else 
			{
				return E_FAIL;
			}
		}

		POSITION Next(const POSITION pos)
		{
			if (pos.pNode && (pos.pNode->next != &m_anchor))
			{
				return POSITION(pos.pNode->next);
			}
			else
			{
				return POSITION(NULL);
			}
		}

		// Remove an item at a position. 
		// The item is returns in ppItem, unless ppItem is NULL.
		// NOTE: This method invalidates the POSITION object.
		HRESULT Remove(POSITION& pos, T *ppItem)
		{
			if (pos.pNode)
			{
				// Remove const-ness temporarily...
				Node *pNode = const_cast<Node*>(pos.pNode);

				pos = POSITION();

				return RemoveItem(pNode, ppItem);
			}
			else
			{
				return E_INVALIDARG;
			}
		}

	};


	// Typical functors for Clear method.

	// ComAutoRelease: Releases COM pointers.
	// MemDelete: Deletes pointers to new'd memory.

	class ComAutoRelease
	{
	public: 
		void operator()(IUnknown *p)
		{
			if (p)
			{
				p->Release();
			}
		}
	};

	class MemDelete
	{
	public: 
		void operator()(void *p)
		{
			if (p)
			{
				delete p;
			}
		}
	};


	// ComPtrList class
	// Derived class that makes it safer to store COM pointers in the List<> class.
	// It automatically AddRef's the pointers that are inserted onto the list
	// (unless the insertion method fails). 
	//
	// T must be a COM interface type. 
	// example: ComPtrList<IUnknown>
	//
	// NULLABLE: If true, client can insert NULL pointers. This means GetItem can
	// succeed but return a NULL pointer. By default, the list does not allow NULL
	// pointers.

	template <class T, bool NULLABLE = FALSE>
	class ComPtrList : public List<T*>
	{
	public:

		typedef T* Ptr;

		void Clear()
		{
			List<Ptr>::Clear(ComAutoRelease());
		}

		~ComPtrList()
		{
			Clear();
		}

	protected:
		HRESULT InsertAfter(Ptr item, Node *pBefore)
		{
			// Do not allow NULL item pointers unless NULLABLE is true.
			if (!item && !NULLABLE)
			{
				return E_POINTER;
			}

			if (item)
			{
				item->AddRef();
			}

			HRESULT hr = List<Ptr>::InsertAfter(item, pBefore);
			if (FAILED(hr))
			{
				SafeRelease(&item);
			}
			return hr;
		}

		HRESULT GetItem(const Node *pNode, Ptr* ppItem)
		{
			Ptr pItem = NULL;

			// The base class gives us the pointer without AddRef'ing it.
			// If we return the pointer to the caller, we must AddRef().
			HRESULT hr = List<Ptr>::GetItem(pNode, &pItem);
			if (SUCCEEDED(hr))
			{
				assert(pItem || NULLABLE);
				if (pItem)
				{
					*ppItem = pItem;
					(*ppItem)->AddRef();
				}
			}
			return hr;
		}

		HRESULT RemoveItem(Node *pNode, Ptr *ppItem)
		{
			// ppItem can be NULL, but we need to get the
			// item so that we can release it. 

			// If ppItem is not NULL, we will AddRef it on the way out.

			Ptr pItem = NULL;

			HRESULT hr = List<Ptr>::RemoveItem(pNode, &pItem);

			if (SUCCEEDED(hr))
			{
				assert(pItem || NULLABLE);
				if (ppItem && pItem)
				{
					*ppItem = pItem;
					(*ppItem)->AddRef();
				}

				SafeRelease(&pItem);
			}

			return hr;
		}
	};
}

